package leetcode_5000;

import java.util.Arrays;


/**
 *@author 周杨
 *VideoStitching_5019 给一个数组里面保存时间片段 start-end 给一个正整数 问最后能划分的最小片段数
 *describe:动态规划
 *2019年4月7日 下午13:49 AC 100%
 */
public class VideoStitching_5019 {
	public static void main(String[] args) {
		VideoStitching_5019 test = new VideoStitching_5019();
		int []i1 = new int[] {5,7};
		int []i2 = new int[] {1,8};
		int []i3 = new int[] {0,0};
		int []i4 = new int[] {2,3};
		int []i5 = new int[] {4,5};
		int []i6 = new int[] {0,6};
		int []i7 = new int[] {5,10};
		int []i8 = new int[] {7,10};
		System.out.println(test.videoStitching(new int[][] {i1,i2,i3,i4,i5,i6,i7,i8}, 5));
	}
	
	public int videoStitching(int[][] clips, int T) {
		int max = -1;
        for(int [] clip:clips) {
        	max = Math.max(max, clip[1]);
        }
        if(max < T) return -1;
        Arrays.sort(clips,(o1,o2)->o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]);
        if(clips[0][0] != 0) return -1;
        int[]dp = new int[T+1];
        Arrays.fill(dp, Integer.MAX_VALUE);//全部不可达
        for(int[] now:clips) {
        	if(now[0] == 0) {
        		for(int i=0;i<=Math.min(T, now[1]);++i) {
        			dp[i] = 1;
        		}
        	}else {
        		if(now[0]>T) continue;
        		if(dp[now[0]] == Integer.MAX_VALUE) return -1;
        		int before = dp[now[0]];
        		for(int i=now[0]+1;i<=Math.min(T, now[1]);++i) {
        			dp[i] = Math.min(dp[i], 1+before);
        		}
        	}
        }
        return dp[T];
    }
}
